Masala #R105D

Jahonali va Timur Codeforces’ga juda qiziqish bilan qaraydigan do‘stlar. Ularning bir nechta Codeforces akkaunti bor, lekin ular qiziqarli “reyting o‘yini” o‘ylab topishdi: akkauntlarni bir-birlariga almashtirib olib, navbat bilan yurish qilishadi.

Boshlang‘ich holatda har bir akkauntda ma’lum bir butun reyting bor. Reytinglar ma'lum bir ketma-ketlikda joylashtirilgan va sizga massiv ko'rinishida beriladi.

Jahonali 1-harakat qiladi, keyin Timur, keyin Jahonali va hokazo navbat bilan.

Har bir o'yinchi o'z navbatida quyidagi amalni bajarishi kerak: 1 ta index tanlab undagi elementni 1 ga oshira yoki tushira oladi.

Jahonali o‘yin davomida quyidagi maqsadni ko‘zlaydi: barcha N akkauntning ratinglari ketma-ket joylashganda “o'zgaruvchan” shaklga kelsin, ya’ni:

Har bir indexdagi son oldidagi ikkala sondan ham qat'iy ravishda katta yoki ikkalasidan ham qat'iy ravishda kichik bo'lishi kerak.

Agar o'yinning qaysidir qismida ushbu barcha shartlar bajarilib, ratinglar ketma-ketligi o'zgaruvchan bo‘lib qolsa, o‘yin darhol to‘xtaydi va Jahonali g‘olib hisoblanadi.

Timurning maqsadi esa buning oldini olish. Agar u 10^9 ta umumiy harakat (Jahonali va Timur harakatlari qo‘shilganda) davomida ketma-ketlikni o'zgaruvchan holga keltirishni oldini olsa Timur o'yinda yutadi.

Faraz qilamizki, ikkisi ham mukammal o‘ynaydi ya'ni yutishi uchun eng yaxshi yurishlarni bajaradi.

Sizga boshlang‘ich N va har bir akkauntning dastlabki ratinglari beriladi. Siz agar Jahonali yutsa, nechta yurishdan keyin yutishini, Timur yutsa -1 ni chiqaring

1 <= A[i] <= \(10^6\)

1 <= N <= \(2*10^5\)

Note: Massivning ketma-ketligi bir xil turadi, ya'ni sonlar joyini almashtirish mumkin emas.

Birinchi qatorda N - massiv uzunligi. 

Undan keyingi qatorda N ta son - A massiv kiritiladi. 

Agar Jahonali yutsa nechta amalda yutishini, aks holda -1 chiqaring.